#include <iostream>
#include <vector>

using namespace std;

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void SelectionSort(vector<int> &arr)
{
    for (int i = 0; i < arr.size(); i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

void BubbleSort(vector<int> &arr)
{
    // 相邻比较,
    for (int i = arr.size() - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

//并非严格意义上的O（n2）
void InsertionSort(vector<int> &arr)
{
    // 0-0， 0-1， 0-2 0-3 有序
    for (int i = 1; i < arr.size(); i++)
    {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
        {
            swap(arr[j], arr[j - 1]);
        }
    }
}

void Printf(vector<int> &v)
{
    cout << "vector:   ";
    for (auto i : v)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> v = {10, 9, 4, 2, 89, 100, 567, -1};
    Printf(v);
    // SelectionSort(v);
    // BubbleSort(v);
    InsertionSort(v);
    Printf(v);
}